package middle;

import sword.offer.common.Node;

/**
 * 你会得到一个双链表，其中包含的节点有一个下一个指针、一个前一个指针和一个额外的 子指针 。这个子指针可能指向一个单独的双向链表，也包含这些特殊的节点。这些子列表可以有一个或多个自己的子列表，以此类推，以生成如下面的示例所示的 多层数据结构 。
 *
 * 给定链表的头节点head，将链表 扁平化 ，以便所有节点都出现在单层双链表中。让 curr 是一个带有子列表的节点。子列表中的节点应该出现在扁平化列表中的curr 之后 和curr.right之前 。
 *
 * 返回 扁平列表的 head。列表中的节点必须将其 所有 子指针设置为null。
 *
 * 链接：https://leetcode-cn.com/problems/flatten-a-multilevel-doubly-linked-list
 *
 * */
public class FlattenAMultilevelDoublyLinkedList {
    /**
     * 递归
     * curr结点如果存在child结点，那么curr.right = child。  child是一个单独的链表，这个链表的最后一个结点应当指向curr.right，即childLastNode.right = curr.right
     * 递归将每一层的链表都进行扁平化
     * 1. 判断node 是否存在child结点，如果存在则进入child所在的链表
     * 2. 当前层如果没有包含child结点的Node了，那么就返回该层的right，回溯到上一层
     * 3. 拿到child链表的尾结点，让其right指向当前结点的right
     * 4. 当前结点的right指向child结点，且curr指向当前结点的right结点
     * */
    class Solution {
        public Node flatten(Node head) {
            if(head == null){
                return null;
            }
            recur(head);
            return head;
        }

        Node recur(Node head){
            Node curr = head;
            Node pre = null;
            while(curr != null){
                if(curr.child != null){
                    Node tempNode = curr.right;
                    curr.right = curr.child;
                    curr.child.left = curr;
                    Node childTail = recur(curr.child);
                    curr.child = null;
                    pre = curr;
                    curr = childTail;
                    if(tempNode == null){
                        continue;
                    }
                    childTail.right = tempNode;
                    tempNode.left = childTail;
                    pre = curr;
                    curr = tempNode;
                }else{
                    pre = curr;
                    curr = curr.right;
                }

            }
            return pre;
        }
    }
}
